package org.ycsoft.PathComputation;

import java.io.FileOutputStream;
import java.io.IOException;
import java.util.*;

import org.ycsoft.MetroidReader.Commons;

/**
 * Contains the shortest paths tree of a single source stop
 * @author allad
 *
 */
public class ShortestPathTree {
	
	private Stop source;
	//private int totalStops = 0; //total number of stops
	Map<Stop,Stop> previousStop = new HashMap<Stop,Stop>();
	Map<Stop,Integer>  distances = new HashMap<Stop,Integer>();  //distances to root
	Map<Stop,Line> backEdgesLines = new HashMap<Stop, Line>(); //lines to which back edges belong to
	
	public ShortestPathTree(Stop root,StopDB stopsDB){
		if(root == null)
			throw new NullPointerException("ShortestPath() : null root stop.");
		this.source = root;
		previousStop.put(source, NullValues.STOP_NULL); //the previous stop of the root is NUll
		for(Stop stop : stopsDB.getStopsSet()){
			if(stop.equals(root)){
				distances.put(root, 0);
			}
			else {
				distances.put(stop, Commons.INFINITY);
			}
			backEdgesLines.put(stop, NullValues.LINE_NULL);
		}
	}
	
	/**
	 * Put the previous stop of a stop in this shortest paths tree
	 * @param stop 
	 * @param previous
	 */
	public void putPrevious(Stop stop,Stop previous){
		if(stop != source){
			previousStop.put(stop, previous);
		}
	}
	
	/**
	 * Update the known distance to the given stop
	 * @param stop Stop whose distance to update
	 * @param distance Currently known distance
	 */
	public void putDistance(Stop stop,int distance){
		if(stop != source){
			distances.put(stop, distance);
		}
	}
	
	/**
	 * Updates the line to which the back edge of this stop belongs to
	 * @param stop Stop whose back edge to update
	 * @param line Back edge line
	 */
	public void putBackEdgeLine(Stop stop,Line line){
		if(stop != source){
			backEdgesLines.put(stop, line);
		}
	}
	
	/**
	 * Returns the current know distance to source of the given stop.
	 * If the distance for that stop is not known, returns INFINITY
	 * @param stop
	 * @return The distance to the root if known or INFINITY otherwise
	 */
	public int getDistance(Stop stop){
		if(distances.containsKey(stop)){
			return distances.get(stop);
		}
		else return Commons.INFINITY;
	}
	
	public Line getBackEdgeLine(Stop stop){
		if(backEdgesLines.containsKey(stop))
			return backEdgesLines.get(stop);
		else return null;
	}
	
	/* (non-Javadoc)
	 * @see java.lang.Object#toString()
	 */
	public String toString(){
		StringBuilder sb = new StringBuilder();
		
		sb.append("Root - "+source+"\n");
		
		for(Stop stop : previousStop.keySet()){
			if(stop == null){
				sb.append("null+\n");
			}
			else sb.append(stop.toString()+"|"+stop.getStopId()+" - "+previousStop.get(stop)+","+distances.get(stop)+" - "+backEdgesLines.get(stop)+"\n");
		}
		
		return sb.toString();
	}

//	public String toMetroid() {
//		StringBuilder sb = new StringBuilder();
//		sb.append("tree "+source.getStopId()+Commons.LINE_SEPARATOR);
//		
//		//classement des stops par ordre croissant d'id dans un tableau
//		int total = previousStop.size();
//		Stop[] temp = new Stop[total];
//		for(Stop stop : previousStop.keySet()){
//			int id = stop.getStopId();
//			temp[id-1] = stop;
//		}
//		
//		//écriture lignes
//		for(int i=0;i<temp.length;i++){
//			Stop stop = temp[i];
//			sb.append(String.format(Commons.formatNumber(stop.getStopId(),Commons.ID_DIGITS_NB)+":"+Commons.formatNumber(previousStop.get(stop).getStopId(),Commons.ID_DIGITS_NB)+","+Commons.formatNumber(distances.get(stop),Commons.LENGTH_DIGITS_NB)+","+Commons.formatNumber(backEdgesLines.get(stop).getLineId(), Commons.ID_DIGITS_NB)));
//			sb.append(Commons.LINE_SEPARATOR);
//		}
//	
//		sb.append("end"+Commons.LINE_SEPARATOR);
//
//		return sb.toString();
//	}
	
	public long toMetroid(FileOutputStream fos) throws IOException{	
		long position = 0;
		
		StringBuilder sb = new StringBuilder();
		sb.append("tree "+source.getStopId()+Commons.LINE_SEPARATOR);
		
		position += CityMap.writeDown(sb.toString(), fos);
		
		//classement des stops par ordre croissant d'id dans un tableau
		int total = previousStop.size();
		Stop[] temp = new Stop[total];
		for(Stop stop : previousStop.keySet()){
			int id = stop.getStopId();
			temp[id-1] = stop;
		}
		
		//écriture lignes
		for(int i=0;i<temp.length;i++){
			Stop stop = temp[i];
			
			position += writePackedBits(stop.getStopId(), previousStop.get(stop).getStopId(), backEdgesLines.get(stop).getLineId(), distances.get(stop), fos);
			
		}
		
		
		sb = new StringBuilder();
		sb.append("end"+Commons.LINE_SEPARATOR);
		position += CityMap.writeDown(sb.toString(), fos);
		
		return position; 
	}

	
	private long writePackedBits(int stopId,int prevId,int lineId,int length,FileOutputStream fos) throws IOException{
		//Les 4 infos sont packées dans 48bits sous la forme
		//0| StopID(10)|PrevID(10)|LineID(11)|LENGTH(16)
		
		//StopId,PrevId are written in 10 bits.Thus a stop can be as big as 1024
		//Lineid is written in 11 bits. Thus a lineId cannot be higher than 2048
		//StopId,PrevId and LineId are packed in the rightmost 31 bits of an int
		//The leftmost bits is untouched
		//61 est représenté par 1111 1111 dans la position adéquate
		if(stopId != -1){
			stopId <<= 21;
			stopId = stopId & Commons.STOP_MASK;		
		}
		else stopId = Commons.STOP_MASK;
			
		if(prevId != -1){
			prevId <<= 11;
			prevId = prevId & Commons.PREV_MASK;	
		}
		else prevId = Commons.PREV_MASK;
		
		if(lineId != -1){
			lineId = lineId & Commons.LINE_MASK;
		}
		else lineId = Commons.LINE_MASK;
		
		//Couper le int en 4 packets de 8 bits
		int part1 = stopId | prevId | lineId;
		byte part1a = (byte)((part1 & 0xFF000000)>>24);  //leftmost bits
		byte part1b = (byte)((part1 & 0x00FF0000)>>16);      
		byte part1c = (byte)((part1 & 0x0000FF00)>>8);
		byte part1d = (byte)(part1 & 0x000000FF);  //rightmost bits
		
		//La longeur d'un trajet ne peut pas être supérieur 31767s soit 9,04H
		short part2 = (short)length;
		//Coupé en 2 packet de 8bits
		byte part2a = (byte)((part2 & 0xFF00)>>8);
		byte part2b = (byte)(part2 & 0x00FF);
		
		byte[] b = new byte[]{part1a,part1b,part1c,part1d,part2a,part2b};
		
		fos.write(b);
		
		return 6;
	}
}
